package com.cskaoyan.com.tree;

import com.cskaoyan.com.mylist.MyArrayList;
import com.cskaoyan.com.queue.MyArrayQueue;
import com.cskaoyan.com.stack.MyArrayStack;

import java.util.ArrayList;
import java.util.List;

/**
 * 使用链表实现一个数据结构为二叉搜索树的数据容器/集合类
 */
public class MyBSTree  <T extends Comparable> {

    private Node root; // MyBSTree底层所持有的二叉搜索树的根结点
    private int size;  // 记录树中存储的元素数目

    /**
     * 二叉搜索树的添加方法
     * @param value: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(T value){
        // 不允许存储null值, 因为null没有办法比较大小
        if (value == null){
            throw new IllegalArgumentException("value = " + value);
        }
        // 树是否为空
        if (isEmpty()){
            root = new Node(value);
            size++;
            return true;
        }

        // 树不空, 添加的是一个叶子位置: 先查找添加的位置, 再添加

        // 查找添加位置: 从根结点向下查找的过程, 找到一个叶子位置

        Node mid = root; // 定义一个临时结点, 用来向下遍历查找数据的添加位置
        Node midF = null; // 定义一个  遍历结点父结点的标记
        int com = 0;

        // mid不是null , 比较大小确定方向, 接着向下找
        while (mid != null){
            // 把  要存储的值  和 当前遍历的结点 存储的内容  进行比较大小
            com = value.compareTo(mid.value);
            midF = mid;
            if (com < 0){
                // 说明: 要存储的value值,  比当前遍历结点存储的值小
                //     ----> 推出, 如果要存储的话, value应该是要存储到mid的left侧
                //     ----> 标记位, 向left移动
                mid = mid.left;
            }else if (com > 0){
                // 说明: 要存储的value值,  比当前遍历结点存储的值大
                //     ----> 推出, 如果要存储的话, value应该是要存储到mid的right侧
                //     ----> 标记位, 向right移动
                mid = mid.right;
            }else {
                // 等于0, 意味着mid存储的内容和新添加的内容, 大小重复
                //  在BSTree上数据重复了, 一般'逻辑'上有三种方式:
                //  1, 计数法
                //  2, 拉链法
                //  3, 修正的BSTree

                return false;// 不允许添加重复数据
            }
        }

        // 要添加结点, 是midF的子结点位置
        if ( com < 0){
            // 说明最后一次比较小于0, value更小, 存在left侧
            midF.left = new Node(value);
        }else {
            // 说明最后一次比较大于于0, value更大, 存在right侧
            midF.right = new Node(value);
        }

        size++;
        return true;
    }

    /**
     * MyBSTree的删除方法
     * @param value: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(T value){
        // 判断树是否为空
        if (isEmpty()){
            throw new RuntimeException("tree is empty");
        }
        // 判断删除的是否是null
        if (value == null){
            throw new IllegalArgumentException("value = " + value);
        }


        // 查找要删除结点.
        Node mid = root; // 定义一个遍历查找结点
        Node midF = null; // 定义一个 查找结点的父结点标记

        while (mid != null){
            // 用要查找的内容 和  当前遍历结点比较大小
            int com = value.compareTo(mid.value);

            if (com < 0){
                // value更小, 向left方向查找
                midF = mid;
                mid = mid.left;
            }else if (com > 0){
                // value值更大, 向right方向查找移动
                midF = mid;
                mid = mid.right;
            }else {
                // value值和 mid存储的内容, 大小相同,  找到了
                // mid标记找到的结点
                break;
            }
        }
        // 上述循环有两个结束条件
        // 1, mid == null  ---> 意味着遍历到树的底层结束都没有找到要删除的内容
        // 2, 找到了, mid就是要找的内容

        if (mid == null){
            // 这个树中没有存储, 要删除的内容
            return false;
        }

        // 找到了mid这个要删除的内容


        // 判断这个找到的要删除的结点是否为双分支 :  是否左右孩子都有
        if (mid.left != null && mid.right != null){
            // 先替换: 选择right子树最小值

            // 找mid的right子树的最left结点
            Node rightMin = mid.right;
            Node rightMinF = mid;
            // 向left移动
            while (rightMin.left != null){
                rightMinF = rightMin;
                rightMin = rightMin.left;
            }

            // 走到这 rightMin就是 要删除的双分支结点的right子树的最小值
            //  接下来:  替换 , 删除

            // 替换
            mid.value = rightMin.value;

            // rightMinF.left = null;// 错误
            // rightMinF.left = rightMin.right;// 不对
            // 我们能不能确定  rightMin 是  rightMinF 的left?   不能
            // 不想在这处理的, 因为太麻烦了

            mid = rightMin;
            midF = rightMinF;
        }


        // mid标记要删除结点: 必然要么是叶子, 要么是单分支
        // 删除叶子 或者  单分支 --->  孩子上移

        // mid是个叶子 --> ch 是 null
        // mid是个单分支  -->  ch  就是这个单分支结点的那个非空孩子
        Node ch = mid.left != null ? mid.left : mid.right;

        // 特殊情况:  删除的是根结点 同时 根结点是单分支结点
        // 判断依据:  midF走到设是不是null
        if (midF == null){
            // 删除的是根结点 同时 根结点是单分支结点
            root = ch;
            size--;
            return true;
        }


        // 上移
        if (mid == midF.left){
            // 要删的结点是其父结点的left
            midF.left = ch;
        }else {
            // 要删除结点是其父结点的right
            midF.right = ch;
        }
        size--;

        return true;
    }


    /**
     * 根据内容的查找方法
     * @param value: 要查找的内容
     * @return: 是否存在
     */
    public boolean contains(T value){
        // 判断树是否为空
        if (isEmpty()){
            throw new RuntimeException("tree is empty");
        }
        // 判断删除的是否是null
        if (value == null){
            throw new IllegalArgumentException("value = " + value);
        }

        Node mid = root; // 定义一个遍历结点

        // 当前遍历结点存在,  比较
        while (mid != null){
            int com = value.compareTo(mid.value);
            if (com > 0){
                // value值更大, 如果存在, 在mid的right侧
                mid = mid.right;
            }else if (com < 0){
                // value值更小, 如果存在, 在mid的left侧
                mid = mid.left;
            }else {
                // value值 和当前遍历的mid存储的内容相等
                return true;
            }
        }

        return false;
    }


    // ----------------为了练习代码:实现一些树操作的方法----------------


    /**
     * 二叉树 层级遍历
     * @return: 层级遍历的结果
     */
    public MyArrayList<T> leOrder(){
        // 定义一个存储遍历结果的容器
        MyArrayList<T> list = new MyArrayList<>();

        // 需要一个用来遍历的辅助容器: 队列
        MyArrayQueue<Node> queue = new MyArrayQueue<>();

        // 1, 根结点入队列
        queue.offer(root);
        // 2, 循环: 队列不空
        while (!queue.isEmpty()){
            // 出队列
            Node poll = queue.poll();
            // 遍历
            list.add(poll.value);
            // 把出队列结点的左右孩子入队列
            if (poll.left != null){
                queue.offer(poll.left);
            }
            if (poll.right != null){
                queue.offer(poll.right);
            }
        }
        return list;
    }



    public MyArrayList<T>  preOrder(){
        // 需要一个存储遍历结果的容器
        MyArrayList<T> list = new MyArrayList<>();

        // 需要一个辅助遍历的容器: 栈
        MyArrayStack<Node> stack = new MyArrayStack<>();

        // 1, 根结点入栈
        stack.push(root);

        // 2, 循环: 栈不空
        while (!stack.isEmpty()){
            // 出栈一个结点
            Node pop = stack.pop();
            // 遍历
            list.add(pop.value);
            // 把出栈结点的右 左孩子入栈
            if (pop.right != null){
                stack.push(pop.right);
            }
            if (pop.left != null){
                stack.push(pop.left);
            }
        }

        return list;
    }


    /**
     * 递归实现: 二叉树的前序遍历
     * @return: 前序遍历的结果
     */
    public MyArrayList<T> preOrder2(){
       // 容器
        MyArrayList<T> list = new MyArrayList<>();

        preOrder2(root, list);

        return list;
    }
    private void preOrder2(Node node, MyArrayList<T> list){
        // node是null: 结束
        if (node == null){
            return;
        }
        // 先序: 根 ,  左  , 右

        // 遍历根
        list.add(node.value);

        // 假设递归,能正常出结果
        // 遍历左子树
        preOrder2(node.left,  list);
        // 遍历右子树
        preOrder2(node.right,  list);
    }


    /**
     * 栈实现二叉树的后序遍历
     * @return: 后序遍历的结果
     */
    public MyArrayList<T>  postOrder(){
        // 需要一个存储遍历结果的容器
        MyArrayList<T> list = new MyArrayList<>();

        // 需要一个用来遍历的辅助容器: 栈
        MyArrayStack<Node> stack = new MyArrayStack<>();


        // 1, 根结点入栈
        stack.push(root);

        // 2, 循环: 栈不空
        while (!stack.isEmpty()){
            // 出栈一个数据
            Node pop = stack.pop();
            // 头插法遍历
            list.add(0, pop.value);
            // 把出栈结点的左右孩子入栈
            if (pop.left != null){
                stack.push(pop.left);
            }
            if (pop.right != null){
                stack.push(pop.right);
            }
        }

        return list;
    }


    /**
     * 递归实现后序遍历
     * @return: 后序遍历的结果
     */
    public MyArrayList<T> postOrder2(){
        MyArrayList<T> list = new MyArrayList<>();

        postOrder2(root, list);

        return list;
    }

    private void  postOrder2(Node node, MyArrayList<T> list){
        if (node == null){
            return;
        }
        // 后序递归遍历: 左, 右 , 根

        // 遍历左子树
        postOrder2(node.left, list);
        // 遍历右子树
        postOrder2(node.right, list);
        // 遍历根结点
        list.add(node.value);
    }


    /**
     * 栈实现二叉树的中序遍历
     * @return: 遍历结果
     */
    public MyArrayList<T> inOrder(){
        // 存储遍历结果的容器
        MyArrayList<T> list = new MyArrayList<>();
        // 用来遍历的辅助容器: 栈
        MyArrayStack<Node> stack = new MyArrayStack<>();


        // 1, 定义一个标记结点
        Node mid = root;

        // 2, 循环: 栈不空  或者 标记结点不是null
        while (!stack.isEmpty()  || mid != null){
            // 2.1 把标记结点mid的left序列全入栈
            while (mid != null){
                stack.push(mid);
                mid = mid.left;
            }
            // 2.2 出栈, 遍历
            Node pop = stack.pop();
            //  遍历
            list.add(pop.value);

            // 2.3 把标记结点, 指向出栈结点的right
            mid = pop.right;
        }

        return list;
    }

    /**
     * 递归实现中序遍历
     * @return: 中序遍历的结果
     */
    public MyArrayList<T> inOrder2(){
        MyArrayList<T> list = new MyArrayList<>();

        inOrder2(root, list);

        return list;
    }

    private void  inOrder2(Node node, MyArrayList<T> list){
        if (node == null){
            return;
        }
        // 中序递归遍历: 左,  根, 右 ,

        // 遍历左子树
        inOrder2(node.left, list);
        // 遍历根结点
        list.add(node.value);
        // 遍历右子树
        inOrder2(node.right, list);

    }


    // 建树操作

    /**
     * 二叉搜索树, 根据先序和中序的建树操作
     * @param preOrder: 先序序列
     * @param inOrder: 中序序列
     */
    public void buildTreeByPreAndInOrder(ArrayList<T> preOrder, ArrayList<T> inOrder) {

        root = buildTreeByPreAndInOrder2(preOrder, inOrder);
        size = preOrder.size();
    }
    // 根据指定序列(前序+中序), 构建一个树, 返回这个树的根结点
    private Node buildTreeByPreAndInOrder2(List<T> preOrder, List<T> inOrder) {
        // 出口
        if (preOrder.size() == 0){
            return null;
        }
        if (preOrder.size() == 1){
            return new Node(preOrder.get(0));
        }

        // 1, 第一步: 在先序中找到根的内容
        T rootValue = preOrder.get(0);
        // 2, 确定, 根在中序中的位置
        int tag = inOrder.indexOf(rootValue);


        // 分析:
        // left子树的先序:   1  --  tag
        // left子树的中序:   0  --  tag-1
        // right子树的先序:  tag+1  --  size-1
        // right子树的中序:  tag+1  --  size-1

        // 根据上面分析的范围, 切割left子树和right子树的先序和中序
        List<T> leftPreOrder =  preOrder.subList(1, tag+1);
        List<T> leftInOrder  =  inOrder.subList(0,  tag);

        List<T> rightPreOrder = preOrder.subList(tag+1,  preOrder.size());
        List<T> rightInOrder  = inOrder.subList(tag+1, inOrder.size());

        // List ArrayList 什么关系?  父子关系

        // 递归构建left子树
        Node left = buildTreeByPreAndInOrder2(leftPreOrder, leftInOrder);
        // 递归构建right子树
        Node right = buildTreeByPreAndInOrder2(rightPreOrder, rightInOrder);

        // 构建当前建树的根结点
        Node node = new Node(rootValue);
        node.left = left;
        node.right = right;

        // 此次树构建完毕
        return node;
    }



    /**
     * 二叉搜索树, 根据中序 和 后序 的建树操作
     * @param inOrder: 中序序列
     * @param postOrder: 后序序列
     */
    public void buildTreeByInAndPostOrder(ArrayList<T> inOrder, ArrayList<T> postOrder) {

        root = buildTreeByInAndPostOrder2(inOrder, postOrder);
        size = inOrder.size();
    }
    // 根据指定序列(中序 + 后序), 构建一个树, 返回这个树的根结点
    private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
        // 出口
        if (postOrder.size() == 0){
            return null;
        }
        if (postOrder.size() == 1){
            return new Node(inOrder.get(0));
        }

        // 1, 第一步: 在后序中找到根的内容(在后序的最后一个位置)
        T rootValue = postOrder.get(postOrder.size() - 1);
        // 2, 确定, 根在中序中的位置
        int tag = inOrder.indexOf(rootValue);


        // 分析:
        // left子树的中序:   0  --  tag-1
        // left子树的后序:   0  --  tag-1
        // right子树的中序:  tag+1  --  size-1
        // right子树的后序:  tag  --  size-2

        // 根据上面分析的范围, 切割left子树和right子树的中序和后序
        List<T> leftInOrder =  inOrder.subList(0, tag);
        List<T> leftPostOrder  =  postOrder.subList(0,  tag);

        List<T> rightInOrder = inOrder.subList(tag+1, inOrder.size());
        List<T> rightPostOrder  = postOrder.subList(tag, inOrder.size() -1);

        // List ArrayList 什么关系?  父子关系

        // 递归构建left子树
        Node left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
        // 递归构建right子树
        Node right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);

        // 构建当前建树的根结点
        Node node = new Node(rootValue);
        node.left = left;
        node.right = right;

        // 此次树构建完毕
        return node;
    }




    public  boolean isEmpty(){
        return size == 0;
    }

    // 二叉搜索树的结点
    class Node{
        T value;     // 值域
        Node left;   // 左指针域
        Node right;  // 右指针域

        public Node(T value) {
            this.value = value;
        }
    }
}
